package cn.kent.middle;

import sjg.DataStructures.util.SortUtils;

import java.util.Arrays;

/**
 * 215. 数组中的第K个最大元素
 * 先排序，然后直接取对应索引值
 */
public class FindKthLargest {
    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 5;
        SortUtils.print(nums);
        int res = findKthLargest3(nums, k);
        SortUtils.print(nums);
        System.out.println(res);
    }

    /**
     * 堆排序
     */
    public static int findKthLargest3(int[] nums, int k) {
        int len = nums.length;
        // 1.构建大顶堆
        for (int i = len / 2 - 1; i >= 0; i--) {
            // nums.length/2-1 -> 获取非叶子节点, -> 从第一个非叶子节点开始调整为大顶堆
            adjustHeap(nums, i, len);
        }
        for (int i = len - 1; i > 0; i--) {
            // 2. 堆顶元素和堆底元素更换，将大元素沉下去
            swap(nums, i, 0);
            // 3.重新调整结构，使满足堆定义，反复执行 2、3直到整个数组 有序
            adjustHeap(nums, 0, i);
        }
        return nums[len - k];
    }

    private static void swap(int[] nums, int i, int i2) {
        int tmp = nums[i2];
        nums[i2] = nums[i];
        nums[i] = tmp;
    }

    private static void adjustHeap(int[] nums, int i, int length) {
        int tmp = nums[i];
        // 循环1,2，比较
        for (int j = 2 * i + 1; j < length; j = 2 * i + 1) {
            // 1.将左右子节点对比，取出大值
            if (j + 1 < length && nums[j] < nums[j + 1]) {
                j++; // 最大值为右子节点
            }
            // 2.左右子节点最大值和根节点比对，替换最大值
            if (tmp < nums[j]) { // 这里判断必须要用tmp进行比对，因为替换后，原父节点成为子节点，循环内是该子节点(原父节点)的左右子节点
                nums[i] = nums[j]; // 将最大值赋值给根节点 (局部树)
                i = j;
            } else {
                break;
            }
        }
        nums[i] = tmp; // 将temp值放到最终的位置
    }

    /**
     * low，很慢很慢
     * 冒泡排序，直接取值
     */
    public static int findKthLargest(int[] nums, int k) {
        // Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] < nums[j]) {
                    swap(nums, j, i);
                }
            }
        }
        return nums[k - 1];
    }

    /**
     * 2ms
     * 先排序，直接取值
     */
    public static int findKthLargest2(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}
